//#define  _CRT_SECURE_NO_WARNINGS
//
//void ShellSort(int* arr, int size)
//{
//    int gap = size;
//    while (gap > 1)
//    {
//        gap = gap / 3 + 1;
//        for (int i = 0; i < size - gap; i++)
//        {
//            int end = i;
//            int tmp = arr[end + gap];
//            while (end >= 0)
//            {
//                if (arr[end] > arr[end + gap])
//                {
//                    arr[end + gap] = arr[end];
//                }
//                else
//                {
//                    break;
//                }
//                arr[end] = tmp;
//                end -= gap;
//            }
//        }
//    }
//}
//
//int* sortArray(int* nums, int numsSize, int* returnSize)
//{
//    ShellSort(nums, numsSize);
//    *returnSize = numsSize;
//    return nums;
//}